package slidingPuzzle;

import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;

import swing.Tile;

public class SlidingPuzzle {
	private ArrayList<ArrayList<Integer>> puzzleData = new ArrayList<ArrayList<Integer>>();
	private int puzzleSize;
	private static final int SPACE_NUMBER = 0;

	public SlidingPuzzle(int puzzleSize) {
		this.puzzleSize = puzzleSize;
	}
	
	public SlidingPuzzle(int puzzleSize, Tile[][] contents) {
		this.puzzleSize = puzzleSize;
		for (int i = 0; i < contents.length; i++) {
			ArrayList<Integer> tileValueList = new ArrayList<Integer>(contents.length);
			for (int j = 0; j < contents[i].length; j++) {
				String tileFaceValue = contents[i][j].getFace();
				int tileFaceInt = SPACE_NUMBER;
				if (tileFaceValue != null) {
					tileFaceInt = Integer.valueOf(tileFaceValue);
				}
				tileValueList.add(tileFaceInt);
			}
			puzzleData.add(tileValueList);
		}
	}

	public void generate() {
		boolean success = false;
		do {
			success = tryGenerate();
		} while (!success);
	}

	public boolean tryGenerate() {

		int puzzleXRows = this.puzzleSize;
		int puzzleYRows = this.puzzleSize;
		int fullPuzzleSize = puzzleXRows * puzzleYRows;

		Random rand = new Random();

		ArrayList<Integer> anArrayList = new ArrayList<Integer>();
		for (int x = 0; x < fullPuzzleSize; x++) {
			anArrayList.add(x);
		}

		ArrayList<Integer> desArrayList = new ArrayList<Integer>();

		while (!anArrayList.isEmpty()) {
			int randInt = rand.nextInt(anArrayList.size());
			int number = anArrayList.get(randInt);
			anArrayList.remove(randInt);
			desArrayList.add(number);
		}
		ArrayList<ArrayList<Integer>> twoDArrayList = new ArrayList<ArrayList<Integer>>();

		int z = 0;
		for (int x = 0; x < puzzleSize; x++) {
			ArrayList<Integer> yArrayList = new ArrayList<Integer>();
			for (int y = 0; y < puzzleSize; y++) {
				yArrayList.add(desArrayList.get(z));
				z++;
			}
			twoDArrayList.add(yArrayList);
		}
		this.puzzleData = twoDArrayList;
		
		if (!isSolvable()) {
			return false;
		} else {
			return true;
		}

	}

	public void checkFinalResult() {
		int counter = 1;
		int numberMatch = 0;
		fullLoop: for (ArrayList<Integer> xLists : puzzleData) {
			for (int x = 0; x < puzzleSize; x++) {
				if (xLists.get(x) != counter) {
					break fullLoop;
				} else {
					numberMatch++;
					if (numberMatch == puzzleSize * puzzleSize - 1) {
						System.out.println("====Well Done====");
						System.exit(0);
					}
				}
				counter++;
			}
		}
		System.out.println("====Unsolvable Game====");
		System.exit(0);
	}

	public void checkResultForEveryMove() {
		int counter = 1;
		int numberMatch = 0;
		fullLoop: for (ArrayList<Integer> xLists : puzzleData) {
			for (int x = 0; x < puzzleSize; x++) {
				if (xLists.get(x) != counter) {
					break fullLoop;
				} else {
					numberMatch++;
					if (numberMatch == puzzleSize * puzzleSize - 1) {
						System.out.println("====Well Done====");
						System.exit(0);
					}
				}
				counter++;
			}
		}
	}

	public ArrayList<ArrayList<Integer>> getPuzzleData() {
		return this.puzzleData;
	}

	public void setPuzzleData(ArrayList<ArrayList<Integer>> pData) {
		this.puzzleData = pData;
	}

	public Position getPosFromNumber(int number) {
		Position pos = new Position();
		int xPos = -1, yPos = 0;
		for (ArrayList<Integer> xLists : puzzleData) {
			if (xLists.contains(number)) {
				xPos = xLists.indexOf(number);
				break;
			}
			yPos++;
		}
		pos.setX(xPos);
		pos.setY(yPos);
		return pos;
	}

	public void display() {
		System.out.println("=GAME START=");
		for (ArrayList<Integer> eachXLists : puzzleData) {
			System.out.println(eachXLists);
		}
		System.out.println("=--------=");
	}

	public void displayMove() {
		for (ArrayList<Integer> eachXLists : puzzleData) {
			System.out.println(eachXLists);
		}
		System.out.println("=--------=");
	}
	
	private void solveLastTwoColumns(final int rowNumber, SolvedRegion solvedRegion) {
		int currentNumber = ( puzzleSize * rowNumber ) - 1 ;
		Position destPos = new Position();
		destPos.setX(puzzleSize-2);	
		destPos.setY(rowNumber-1);
		numberToPos(currentNumber, destPos.getX() + 1, destPos.getY() + 2);
		moveNumberToPos(currentNumber + 1, destPos);
		numberToPos(currentNumber, destPos.getX(), destPos.getY() + 1);
		numberToPos(currentNumber + 1, destPos.getX() + 1, destPos.getY());
		moveNumberToPos(currentNumber, destPos);
		solvedRegion.addSolvedNumber(currentNumber);
		solvedRegion.addSolvedNumber(currentNumber + 1);
	}

	private void solveFirstColumnsMinus2(final int rowNumber, SolvedRegion solvedRegion) {
		int currentNumber = (puzzleSize * (rowNumber -1) ) + 1 ;
		Position destPos = new Position();
		destPos.setX(0);
		destPos.setY(rowNumber - 1);
		int loopForXArray = puzzleSize - 2;
		while (loopForXArray > 0) {
			moveNumberToPos(currentNumber, destPos);
			solvedRegion.addSolvedNumber(currentNumber);
			destPos.setX(destPos.getX() + 1);
			currentNumber++;
			loopForXArray--;
		}
	}
	
	private void solveFirstPuzzleSizeMinusTwoRows(SolvedRegion solvedRegion) {
		
		int rowNumber = 1 ;
		
		int loopForYArray = puzzleSize - 2;
		while (loopForYArray > 0) {
			// Solve the first puzzlesize - 2 numbers in the current row
			solveFirstColumnsMinus2(rowNumber , solvedRegion);
			solveLastTwoColumns(rowNumber,solvedRegion);
			rowNumber ++;
			loopForYArray--;

		}
	}

	public LinkedList<Move> autoSolve() {
		SolvedRegion solvedRegion = new SolvedRegion();
		solveFirstPuzzleSizeMinusTwoRows(solvedRegion);
		solveLastTwoPuzzleRows(solvedRegion);
		return solveMoves;
	}

	private void solveLastTwoPuzzleRows(SolvedRegion solvedRegion) {
		int currentNumber = ((puzzleSize - 2) * (puzzleSize)) + 1;
		Position destPos = new Position();
		destPos.setY(puzzleSize - 2);
		destPos.setX(0);
		
		for (int x = puzzleSize - 2; x > 0; x--) {
			numberToPos(currentNumber, destPos.getX() + 2, destPos.getY() + 1);
			moveNumberToPos(currentNumber + puzzleSize, destPos);
			numberToPos(currentNumber, destPos.getX() + 1, destPos.getY());
			numberToPos(currentNumber + this.puzzleSize,
					destPos.getX(), destPos.getY() + 1);
			moveNumberToPos(currentNumber, destPos);
			solvedRegion.addSolvedNumber(currentNumber);
			solvedRegion.addSolvedNumber(currentNumber + puzzleSize);
			destPos.setX(destPos.getX() + 1);
			currentNumber++;
		}
		moveNumberToPos(currentNumber, destPos);
		destPos.setX(destPos.getX() + 1);
		currentNumber++;
		moveNumberToPos(currentNumber, destPos);
		if (getPosFromNumber(0).getX() != this.puzzleSize - 1) {
			spaceTileMoveRight();
		}
	}

	public void moveNumberToPos(int number, Position targetPos) {
		Position numberPos = getPosFromNumber(number);

		SolvedRegion solvedRegion = new SolvedRegion();

		while (!numberPos.equals(targetPos)) {
			while (numberPos.getX() < targetPos.getX()) {
				moveNumberRight(number);
				numberPos = getPosFromNumber(number);
			}

			while (numberPos.getY() < targetPos.getY()) {
				moveNumberDown(number);
				numberPos = getPosFromNumber(number);
			}

			
			if (numberPos.getX() > targetPos.getX()) {
				if (solvedRegion.getSolvedNumbers().contains(getNumberFromPos(targetPos))) {
					throw new IllegalStateException("Illegal move");
				} else {
					moveNumberLeft(number);
				}
			}

			if (numberPos.getY() > targetPos.getY()) {

				if (solvedRegion.getSolvedNumbers().contains(getNumberFromPos(targetPos))) {
					throw new IllegalStateException("Illegal move");
				} else {
					moveNumberUp(number);
				}
			}

			numberPos = getPosFromNumber(number);

		}

	}
	
	//move number one  single step
	public void numberToPos(int number, int x, int y) {

		Position targetPos = new Position();
		targetPos.setX(x);
		targetPos.setY(y);

		Position numberPos = getPosFromNumber(number);
		while (!numberPos.equals(targetPos)) {

			if (numberPos.getX() < targetPos.getX()) {
				moveNumberRight(number);

			}

			if (numberPos.getY() < targetPos.getY()) {
				moveNumberDown(number);

			}

			if (numberPos.getY() > targetPos.getY()) {
				moveNumberUp(number);

			}

			if (numberPos.getX() > targetPos.getX()) {
				moveNumberLeft(number);

			}

			numberPos = getPosFromNumber(number);

		}

	}

	private LinkedList<Move> solveMoves = new LinkedList<Move>();
	public void spaceTileMoveUp() {
		int intSpaceXPos = getPosFromNumber(SPACE_NUMBER).getX();
		int intSpaceYPos = getPosFromNumber(SPACE_NUMBER).getY();
		int newYPos = intSpaceYPos - 1;
		if (newYPos > -1) {
			int newPosOriginalValue = this.puzzleData.get(newYPos)
					.get(intSpaceXPos);
			this.puzzleData.get(intSpaceYPos).set(intSpaceXPos,
					newPosOriginalValue);
			this.puzzleData.get(newYPos)
					.set(intSpaceXPos, SPACE_NUMBER);
			solveMoves.add(new Move(intSpaceYPos, intSpaceXPos, newYPos, intSpaceXPos));
//			gui.repaint();
			//this.displayMove();
			//this.checkResultForEveryMove();

		}

	}

	public void spaceTileMoveDown() {
		int intSpaceXPos = getPosFromNumber(0).getX();
		int intSpaceYPos = getPosFromNumber(0).getY();
		int newYPos = intSpaceYPos + 1;
		if (newYPos <= this.puzzleSize - 1) {
			int newPosOriginalValue = this.puzzleData.get(newYPos)
					.get(intSpaceXPos);
			this.puzzleData.get(intSpaceYPos).set(intSpaceXPos,
					newPosOriginalValue);
			this.puzzleData.get(newYPos)
					.set(intSpaceXPos, SPACE_NUMBER);
			solveMoves.add(new Move(intSpaceYPos, intSpaceXPos, newYPos, intSpaceXPos));
//			gui.repaint();
			//this.displayMove();
			//this.checkResultForEveryMove();
		}
	}

	public void spaceTileMoveLeft() {
		int intSpaceXPos = getPosFromNumber(0).getX();
		int intSpaceYPos = getPosFromNumber(0).getY();
		int newXPos = intSpaceXPos - 1;
		if (newXPos > -1) {
			int newPosOriginalValue = this.puzzleData
					.get(intSpaceYPos).get(newXPos);
			this.puzzleData.get(intSpaceYPos).set(intSpaceXPos,
					newPosOriginalValue);
			this.puzzleData.get(intSpaceYPos)
					.set(newXPos, SPACE_NUMBER);
			
			solveMoves.add(new Move(intSpaceYPos, intSpaceXPos, intSpaceYPos, newXPos));
//			gui.repaint();
			//this.displayMove();
			//this.checkResultForEveryMove();

		}
	}

	public void spaceTileMoveRight() {

		int intSpaceXPos = getPosFromNumber(0).getX();
		int intSpaceYPos = getPosFromNumber(0).getY();
		int newXPos = intSpaceXPos + 1;
		if (newXPos <= this.puzzleSize - 1) {
			int newPosOriginalValue = this.puzzleData
					.get(intSpaceYPos).get(newXPos);
			this.puzzleData.get(intSpaceYPos).set(intSpaceXPos,
					newPosOriginalValue);
			this.puzzleData.get(intSpaceYPos)
					.set(newXPos, SPACE_NUMBER);
			solveMoves.add(new Move(intSpaceYPos, intSpaceXPos, intSpaceYPos, newXPos));
//			gui.repaint();
			//this.displayMove();
			//this.checkResultForEveryMove();
		}
	}

	public int getNumberFromPos(Position pos) {
		int number = -1;
		number = this.puzzleData.get(pos.getY()).get(pos.getX());
		return number;
	}

	public void moveNumberLeft(int number) {
		setRestrictNumber(number);
		// Position spacePos = getPos.getNumberPos(SlidingPuzzle.SPACE_NUMBER);
		Position numberPos = getPosFromNumber(number);
		if (numberPos.getX() <= 0) {
			return;
		}
		Position leftPosOfNumber = new Position();
		leftPosOfNumber.setY(numberPos.getY());
		leftPosOfNumber.setX(numberPos.getX() - 1);

		//SpaceTile ms = new SpaceTile(SPACE_NUMBER);

		moveSpaceToPosition(leftPosOfNumber);

		spaceTileMoveRight();
	}

	public void moveNumberUp(int number) {
		setRestrictNumber(number);
		// Position spacePos = getPos.getNumberPos(SlidingPuzzle.SPACE_NUMBER);
		Position numberPos = getPosFromNumber(number);
		Position spacePos = getPosFromNumber(this.SPACE_NUMBER);
		if (numberPos.getY() <= 0) {
			return;
		}
		Position upPosOfNumber = new Position();
		Position downPosOfNumber = new Position();
		upPosOfNumber.setY(numberPos.getY() - 1);
		upPosOfNumber.setX(numberPos.getX());

		downPosOfNumber.setY(numberPos.getY() + 1);
		downPosOfNumber.setX(numberPos.getX());

		//SpaceTile ms = new SpaceTile(SPACE_NUMBER);
		if ((numberPos.getY() != this.puzzleSize - 1) && spacePos.getX() < numberPos.getX()) {
			moveSpaceToPosition(downPosOfNumber);
		}
		moveSpaceToPosition(upPosOfNumber);

		spaceTileMoveDown();
	}

	public void moveNumberDown(int number) {

		setRestrictNumber(number);
		// Position spacePos = getPos.getNumberPos(SlidingPuzzle.SPACE_NUMBER);
		Position numberPos = getPosFromNumber(number);
		if (numberPos.getY() >= this.puzzleSize - 1) {
			return;
		}
		Position downPosOfNumber = new Position();
		downPosOfNumber.setY(numberPos.getY() + 1);
		downPosOfNumber.setX(numberPos.getX());

		moveSpaceToPosition(downPosOfNumber);

		spaceTileMoveUp();
	}

	public void moveNumberRight(int number) {
		setRestrictNumber(number);
		// Position spacePos = getPos.getNumberPos(SlidingPuzzle.SPACE_NUMBER);
		Position numberPos = getPosFromNumber(number);
		if (numberPos.getX() >= this.puzzleSize - 1) {
			return;
		}
		Position leftPosOfNumber = new Position();
		leftPosOfNumber.setY(numberPos.getY());
		leftPosOfNumber.setX(numberPos.getX() + 1);

		moveSpaceToPosition(leftPosOfNumber);

		spaceTileMoveLeft();
	}

	public void moveSpaceToPosition(Position targetPos) {

		Position spacePos = getPosFromNumber(this.SPACE_NUMBER);

		int noLoop = this.puzzleSize * this.puzzleSize;

		while (!spacePos.equals(targetPos)) {

			// moveDown
			while (spacePos.getY() < targetPos.getY()) {
				Position nextMove = new Position();
				nextMove.setY(spacePos.getY() + 1);
				nextMove.setX(spacePos.getX());
				if (isRestriction(nextMove)) {
					if (spacePos.getX() == this.puzzleSize - 1) {
						spaceTileMoveLeft();
					} else {
						spaceTileMoveRight();
					}
				} else {
					spaceTileMoveDown();
				}
				spacePos = getPosFromNumber(this.SPACE_NUMBER);
				if (noLoop > 0) {
					noLoop--;
				} else {
					System.out.println("MoveSpaceToPos DeadLock on moveDown!!!");
					// System.exit(0);
				}
			}

			// moveRight
			while (spacePos.getX() < targetPos.getX()) {
				Position nextMove = new Position();
				nextMove.setX(spacePos.getX() + 1);
				nextMove.setY(spacePos.getY());
				if (isRestriction(nextMove)) {
					if (spacePos.getY() == this.puzzleSize - 1) {
						spaceTileMoveUp();
					} else {
						spaceTileMoveDown();
					}
				} else {
					spaceTileMoveRight();
				}
				spacePos = getPosFromNumber(this.SPACE_NUMBER);
				if (noLoop > 0) {
					noLoop--;
				} else {
					System.out.println("MoveSpaceToPos DeadLock on moveRight!!!");
					break;
					// System.exit(0);
				}
			}

			// MoveLeft

			while (spacePos.getX() > targetPos.getX()) {
				Position nextMove = new Position();
				nextMove.setX(spacePos.getX() - 1);
				nextMove.setY(spacePos.getY());
				if (isRestriction(nextMove)) {
					if (spacePos.getY() == this.puzzleSize - 1) {
						spaceTileMoveUp();
					} else {
						spaceTileMoveDown();
					}
				} else {
					spaceTileMoveLeft();
				}
				spacePos = getPosFromNumber(this.SPACE_NUMBER);
				if (noLoop > 0) {
					noLoop--;
				} else {
					System.out.println("MoveSpaceToPos DeadLock on MoveLeft!!!");
					break;
					// System.exit(0);
				}
			}

			// moveUp
			while (spacePos.getY() > targetPos.getY() && spacePos.getY() > 0) {
				Position nextMove = new Position();
				nextMove.setY(spacePos.getY() - 1);
				nextMove.setX(spacePos.getX());
				if (isRestriction(nextMove)) {
					if (spacePos.getX() == this.puzzleSize - 1) {
						spaceTileMoveLeft();
					} else {
						spaceTileMoveRight();
					}
				} else {
					spaceTileMoveUp();
				}
				spacePos = getPosFromNumber(this.SPACE_NUMBER);
				if (noLoop > 0) {
					noLoop--;
				} else {
					System.out.println("MoveSpaceToPos DeadLock on moveUp!!!");
					// System.exit(0);
				}
			}

		}
	}

	private int movingNumber;

	public void setRestrictNumber(int restrictNumber) {
		this.movingNumber = restrictNumber;
	}

	public boolean isRestriction(Position pos) {

		if (pos.getX() < 0) {
			return true;
		}
		if (pos.getX() > this.puzzleSize - 1) {
			return true;
		}
		if (pos.getY() < 0) {
			return true;
		}
		if (pos.getY() > this.puzzleSize - 1) {
			return true;
		}
		SolvedRegion nip = new SolvedRegion();
		ArrayList<Integer> rightNumbers = nip.getSolvedNumbers();
		int posNumber = getNumberFromPos(pos);

		if (rightNumbers.contains(posNumber)) {
			return true;
		}

		if (getNumberFromPos(pos) == movingNumber) {
			return true;

		}

		return false;
	}

	public boolean isSolvable(){
		ArrayList<Integer> initPuzzleArrayData = create1DFrom2D(puzzleData);
		int index=0;
		int inversionPairs = 0;
		int indexOfBlank = initPuzzleArrayData.indexOf(SPACE_NUMBER);
		while(!initPuzzleArrayData.isEmpty()){
			int num = initPuzzleArrayData.get(0);
			initPuzzleArrayData.remove(index);
			for(int restNumber : initPuzzleArrayData){
				if(num > restNumber && restNumber !=0 ){ 
					inversionPairs ++;
				}
			}
		}
		// if inversionPairs is odd and puzzleSize is odd  game is unsolvable 
		// if inversionPairs is even and puzzleSize + blank row (first row is 0)is odd game is unsolvable  
		
		
		int blankInRow = indexOfBlank / puzzleSize ;
		DecimalFormat decimalFormat = new DecimalFormat("#;(#)");
		decimalFormat.setRoundingMode(RoundingMode.FLOOR);
		
		decimalFormat.format(blankInRow);
		
		
		if(inversionPairs % 2 > 0  && puzzleSize % 2 > 0 ){
			return false;
		}else if((inversionPairs + blankInRow) % 2 == 0 && puzzleSize % 2 == 0 ){
			return false;
		}
		return true;
	}

	private ArrayList<Integer> create1DFrom2D(ArrayList<ArrayList<Integer>> puzzleData2D) {
		ArrayList<Integer> puzzleData1D = new ArrayList<Integer>();
		for(int i=0; i<puzzleData2D.size(); i++){
			puzzleData1D.addAll(puzzleData2D.get(i));
		}
		return puzzleData1D;
	}
	

}
